Motivating examples begin with a torus in 3 dimensional space. 3000 points are sampled randomly and uniformly from the surface of the torus, and we wish to make a 2 dimensional representation of these points such that local structure is preserved, i.e. points that are close together should stay together. We colour the points to give some sense of where they belong.
You must enable Javascript to view this page properly.
The Barnes-Hut algorithm attempts to fit a model with fewer dimensions, preserving local structure. The lower-dimensional model looks a lot like an elastic torus was split open and flattened out, kind of like a popped torus-shaped balloon.
You must enable Javascript to view this page properly.
Now we’ll add a fourth dimension but with linear structure. We can simply add the colour mapping as a fourth dimension, and see if we recover the 3 dimensional structure with the colour mapping in-tact.
You must enable Javascript to view this page properly.
Again, this looks like a torus-shaped balloon has been burst, only in this case it hasn’t been flattened out. This is because of the clustering effect of Barnes-Hut, pulling the evenly distributed points into tighter clusters.
To increase the level of difficulty, let’s make the fourth dimension non-linear. Now the top and bottom of the torus are more similar on the fourth dimension than the bulgy middle.
You must enable Javascript to view this page properly.
You must enable Javascript to view this page properly.
Adding ever more dimensions with non-linear relationships to the existing dimensions
You must enable Javascript to view this page properly.
You must enable Javascript to view this page properly.
We’re up to 6 dimensions, so feasibly we could explore them by looking at every combination (here’s another representation by way of example)
You must enable Javascript to view this page properly.
But for every dimension we add, we have d choose 3 possible spatial representations. If we have 10 dimensions, that’s 120 (or d-1 choose 3 = 84 if we use colour).
You must enable Javascript to view this page properly.